#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;
namespace lnb
{
	template<class T>
	struct HashNode {
		HashNode(const T& kv)
			:_data(kv)
		{}
		HashNode<T>* _next = nullptr;
		T _data;
	};

template<class K, class T, class KeyOfValue>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfValue>
struct __Hash_iterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfValue> hashtable;
	typedef __Hash_iterator<K,T,Ref,Ptr,KeyOfValue> self;
	typedef __Hash_iterator<K, T, T&, T*, KeyOfValue> it;
	__Hash_iterator(Node* node,const hashtable& table)
	:_node(node),_table(table)
	{

	}

	__Hash_iterator(const it& i)
		:_node(i._node),
		_table(i._table)
	{
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}




	self& operator++()
	{
		if (_node->_next)
		{
			_node=_node->_next;
			return *this;
		}
		else
		{
			size_t location = KeyOfValue()(_node->_data) % _table._table.size();
			location++;
			while (location < _table._table.size())
			{
				if (_table._table[location])
				{
					_node = _table._table[location];
					break;
				}
				else
				{
					location++;
				}
			}

			if (location == _table._table.size())
			{
				_node = nullptr;
			}

			return *this;
		}


	}


	bool operator!=(const self& s)
	{
		return _node != s._node;
	}



	Node* _node;
	const hashtable& _table;

};

	







template<class K,class T,class KeyOfValue>
class HashTable
{
	template<class K, class T, class Ref, class Ptr, class KeyOfValue>
	friend struct __Hash_iterator;
public:
	typedef __Hash_iterator<K, T, T&, T*, KeyOfValue> iterator;
	typedef __Hash_iterator<K, T,const T&, const T*, KeyOfValue> const_iterator;


	iterator begin()
	{
		for (auto e : _table)
		{
			if (e)
			{
				return iterator(e,*this);
			}
		}
		return iterator(nullptr, *this);
	}

	iterator end()
	{
		return iterator(nullptr, *this);
	}

	const_iterator begin()const
	{
		for (auto e : _table)
		{
			if (e)
			{
				return const_iterator(e, *this);
			}
		}
		return const_iterator(nullptr, *this);
	}

	const_iterator end()const
	{
		return const_iterator(nullptr, *this);
	}

	typedef HashNode<T> Node;
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		static const size_t primeList[PRIMECOUNT] =
		{
		53ul, 97ul, 193ul, 389ul, 769ul,
		1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
		49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
		1572869ul, 3145739ul, 6291469ul, 12582917ul,
	   25165843ul,
		50331653ul, 100663319ul, 201326611ul, 402653189ul,
	   805306457ul,
		1610612741ul, 3221225473ul, 4294967291ul
		};
		size_t i = 0;
		for (; i < PRIMECOUNT; ++i)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	pair<iterator,bool> insert(const T& data)
	{
		auto ret=Find((KeyOfValue()(data)));
		if ( ret._node!=nullptr)
		{
			return make_pair(ret,false);
		}

		if (_n == _table.size())
		{
			//int newsize = GetNextPrime(_table.size());
			int newsize = _table.size() == 0 ? 10 : _table.size() * 2;
			vector<Node*> v(newsize, nullptr);
			for (auto& cur : _table)
			{
				while (cur)
				{
					Node* next = cur->_next;
					int index= (KeyOfValue()(cur->_data)) % v.size();
					cur->_next=v[index];
					v[index] = cur;
					cur = next;


				}

			}
			_table.swap(v);


		}

		int index = (KeyOfValue()(data)) % _table.size();
		Node* newnode = new Node(data);
		newnode->_next = _table[index];
		_table[index] = newnode;
		_n++;
		return make_pair(iterator(newnode,*this),true);
	}

	iterator Find(const K& key)
	{
		if (_table.size() == 0)
		{
			return iterator(nullptr,*this);
		}
		int index = key % _table.size();
		Node* cur = _table[index];
		while (cur)
		{
			if ((KeyOfValue()(cur->_data)) == key)
			{
				return iterator(cur, *this);
			}
			else
			{
				cur = cur->_next;
			}
		}
		return iterator(nullptr, *this);

	}


	bool Erase(const K& key)
	{
		if (!Find(key))
		{
			return false;
		}
		
		int index = key % _table.size();
		Node* cur = _table[index];
		Node* prev =nullptr;
		while (cur)
		{
			if ((KeyOfValue()(cur->_data)) == key)
			{
				if (prev == nullptr)
				{
					_table[index] = cur->_next;
				}
				else
				{
					auto next = cur->_next;
					prev->_next = next;
				}
				delete cur;
				--_n;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}


		}



		return false;


	}


	~HashTable()
	{
		for (auto cur : _table)
		{
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
		}
		_n = 0;
		_table.~vector();
	}



private:
	vector<Node*> _table;
	int _n=0;

};

//void Test()
//	{
//		int arr[] = { 3,33,2,13,5,12,1002 };
//		HashTable<int, pair<int,int>> h;
//		for (auto e : arr)
//		{
//			h.insert(make_pair(e, e));
//		}
//		h.insert(make_pair(15, 15));
//		h.insert(make_pair(25, 25));
//		h.insert(make_pair(35, 35));
//		h.insert(make_pair(45, 45));
//	}
//


}